<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      class Node {
        constructor(key) {
          this.key = key;
          this.left = null; // 左指针
          this.right = null; // 右指针
        }
      }
      // 用来标记计算结果
      const compare = {
        LESS_THAN: -1, // 小于
        BIGGER_THAN: 1, // 大于
        EQUALS: 0, // 等于
      };

      // 封装二叉树
      class BST {
        constructor() {
          // 根节点
          this.root = null;
        }

        // -----------------------------------------------------------------------------------------
        // 添加方法
        insert(value) {
          // 判断情况 根节点是否为空
          if (this.root == null) {
            this.root = new Node(value);
          } else {
            // 此时  需要使用递归  因为不知道二叉树的深度  所以需要一直去判断
            this.insertNode(this.root, value);
          }
        }

        // 单独封装一个方法 用来判断如果添加的value比原来的node小  那么添加到左节点 否则去右节点
        insertNode(node, value) {
          // 如果是小于的情况
          if (this.compareFn(value, node.key) === compare.LESS_THAN) {
            if (node.left == null) {
              // 到最后一层停止
              node.left = new Node(value);
            } else {
              // 一直递归调用
              this.insertNode(node.left, value);
            }
          } else {
            if (node.right == null) {
              node.right = new Node(value);
            } else {
              this.insertNode(value, node.right);
            }
          }
        }

        // 计算方法单独封装
        compareFn(a, b) {
          if (a === b) {
            return compare.EQUALS;
          }
          return a < b ? compare.LESS_THAN : compare.BIGGER_THAN;
        }

        // ----------------------------------------------------------------------------------------------------------
        /*   
        - 中序遍历是一种以上行顺序访问 BST 所有节点的遍历方式，也就是以从最小到最大的顺序
          访问所有节点。 中序遍历的一种应用就是对树进行排序操作。
        - 先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构
          化的文档。
        - 后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目
          录及其子目录中所有文件所占空间的大小。 
        */

        // 中序遍历
        inOrderMap(callback) {
          this.inOrderMapNode(this.root, callback);
        }

        /* 
        真正的执行函数抽离出来
        核心思想: 先遍历所有左节点直到没有元素 那么此时就是最小的元素  再打印对应的上级节点 其次是右节点  来实现从小到大的排序 
        */
        inOrderMapNode(node, callback) {
          // 终止递归 查不到元素
          if (node != null) {
            // 先递归左节点
            this.inOrderMapNode(node.left, callback);
            callback(node.key);
            this.inOrderMapNode(node.right, callback);
          }
        }


        // 先序遍历
        preOrderMap(callback) {
          this.preOrderMapNode(this.root, callback);
        }

        preOrderMapNode(node, callback) {
          // 终止递归 查不到元素
          if (node != null) {
            // 先递归父节点
            callback(node.key);
            this.preOrderMapNode(node.left, callback);
            this.preOrderMapNode(node.right, callback);
          }
        }

        // 后序遍历
        pastOrderMap(callback) {
          this.pastOrderMapNode(this.root, callback);
        }
        pastOrderMapNode(node, callback) {
          // 终止递归 查不到元素
          if (node != null) {
            this.pastOrderMapNode(node.left, callback);
            this.pastOrderMapNode(node.right, callback);
            callback(node.key);
          }
        }


      }

      const tree = new BST();

      tree.insert(100);
      tree.insert(90);
      tree.insert(88);
      tree.insert(98);
      tree.insert(108);

      tree.inOrderMap((value) => {
        // console.log(value);
      });
      tree.preOrderMap((value)=> {
        // console.log(value);
      })
      tree.pastOrderMap((value)=> {
        console.log(value);
      })

    </script>
  </body>
</html>
